#include <stdio.h>
#include <stdlib.h>

typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode, *LinkList;

//********************************************************************************************
//不带头结点的单链表
bool InitList(LinkList &L)
{
    L = NULL;
    return true;
}

bool ListInsert(LinkList &L, int i, int e)
{
    if (i < 1)
    {
        return false;
    }
    if (i == 1)
    {
        LNode *m = (LNode *)malloc(sizeof(LNode));
        m->data = e;
        m->next = L;
        L = m;
        return true;
    }
    LNode *p;
    int j = 1; //指向当前第几个结点
    p = L;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL) //插入位置不合法
    {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

//前插操作
bool InsertPriorNode(LNode *p, int e)
{
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) //内存分配失败
    {
        return false;
    }

    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e; //把p结点的值改为当前结点
    return true;
}

//********************************************************************************************
//带头结点
bool InitList2(LinkList &L)
{
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL)
    {
        return false;
    }
    L->next = NULL;
    return true;
}

//按位置插入
bool ListInsert2(LinkList &L, int i, int e)
{
    if (i < 1)
    {
        return false;
    }
    LNode *p;
    int j = 0; //指向当前第几个结点
    p = L;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL) //插入位置不合法
    {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

//删除结点
bool ListDlete2(LinkList &L, int i, int &e)
{
    //先找到要删除的结点
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL || p->next == NULL)
    {
        return false;
    }
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

//按位查找
LNode *GetElem2(LinkList L, int i)
{
    if (i < 0)
    {
        return NULL;
    }
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}

//按值查找
LNode *LocateElem2(LinkList L, int e)
{
    LNode *p = L->next;
    while (p != NULL && p->data != e)
    {
        p = p->next;
    }
    return p;
}

//输出
void print2(LinkList L)
{
    LNode *p = L;
    while (p->next != NULL)
    {
        printf("%d\t", p->next->data);
        p = p->next;
    }
}

int main()
{
    printf("\n\n========================================================================\n\n");
    LinkList L;
    InitList2(L);
    ListInsert2(L, 1, 3);
    print2(L);
    printf("\n\n========================================================================\n\n");
    return 0;
}